package 每日一题OJ;

/**
 * @author shy_black
 * @date 2019/8/24 15:32
 * @Description:
 */
public class _300_最长上升子序列 {

    //dp解法，利用一位数组，双重循环，记录在i之前的最长上升子序列，从而得到全部数组的最长上升子序列
//class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length <= 0)
            return 0;
        if (nums.length == 1) {
            return 1;
        }
        int[] arr = new int[nums.length];
        arr[0] = 1;
        int max = 0;
        // int max = 1;
        //i表示dp中的比较到哪一个数字了，
        for (int i = 1; i < nums.length; i++) {
            int tmp = 0;
            //j表示0-i直接的比较
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    tmp = Math.max(tmp, arr[j]);
                }
            }
            arr[i] = tmp + 1;
            max = Math.max(arr[i], max);
        }
        return max;
    }


    //带二维数组的可记忆写法，减掉了每次递归时候很多无用的重复操作
//class Solution {
    public int lengthOfLIS_1(int[] nums) {
        int list[][] = new int[nums.length + 1][nums.length];
        for (int i = 0; i < nums.length + 1; i++) {
            for (int j = 0; j < nums.length; j++) {
                list[i][j] = -1;
            }
        }
        return fun(nums, list, -1, 0);
    }

    private static int fun(int[] nums, int[][] list, int pre, int cur) {
        if (cur == nums.length)
            return 0;

        if (list[pre + 1][cur] >= 0)
            return list[pre + 1][cur];

        int take = 0;

        if (pre < 0 || nums[pre] < nums[cur])
            take = 1 + fun(nums, list, cur, cur + 1);
        int nottake = 0;
        nottake = fun(nums, list, pre, cur + 1);
        list[pre + 1][cur] = Math.max(take, nottake);
        return list[pre + 1][cur];
    }

    //暴力递归写法
//class Solution {
    public int lengthOfLIS_2(int[] nums) {
        if (nums.length <= 0)
            return 0;
        if (nums.length == 1)
            return 1;
        return fun(nums, Integer.MIN_VALUE, 0);
    }

    private static int fun(int[] nums, int pre, int cur) {
        if (cur == nums.length)
            return 0;
        int take = 0;
        if (pre < nums[cur])
            take = 1 + fun(nums, nums[cur], cur + 1);
        int nottake = fun(nums, pre, cur + 1);
        return Math.max(take, nottake);
    }
}